package 竞赛.NO_399;

import java.util.HashMap;
import java.util.Map;

/**
 * 创建时间： 2024-05-26 10:47
 * 用普通的方法根本解不出来，会超时
 **/
public class 优质数对的总数II_100321 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numberOfPairs(new int[]{1, 3, 4}, new int[]{1, 3, 4}, 1));
    }

    static class Solution {
        public long numberOfPairs(int[] nums1, int[] nums2, int k) {
            long ans = 0;
            Map<Integer, Integer> hm = new HashMap<>();
            for (int v : nums2) {
                hm.put(v, hm.getOrDefault(v, 0) + 1);
            }
            for (int v : nums1) {
                if (v % k != 0) {
                    continue;
                }
                v /= k;
                for (int i = 1; i * i <= v; i++) {
                    if (v % i != 0) {
                        continue;
                    }
                    int t = v / i;
                    if (hm.containsKey(i)) ans += hm.get(i);
                    if (hm.containsKey(t) && t != i) ans += hm.get(t);
                }
            }
            return ans;
        }
    }
}
